#include "sort.h"

void _MergeSort(vector<int>& vc, vector<int>& tmp, int begin, int end);

void MergeSort(vector<int>& vc){
  vector<int> tmp;
  tmp.resize(vc.size());

  size_t gap = 1;
  while(gap < vc.size())
  {
    for(size_t i = 0; i < vc.size(); i+=2*gap)
    {
      size_t begin1 = i;
      size_t end1 = begin1+gap;
      size_t begin2 = end1;
      size_t end2 = begin2+gap;

      int k = begin1;
      if(end1 >= vc.size())
      {
        end1 = vc.size();
        while(end1-begin1 > 0)
        {
          tmp[k++] = vc[begin1++];
        }
        continue;
      }
      else if(end2 > vc.size())
      {
        end2 = vc.size();
      }
      

      while(end1-begin1>0 && end2-begin2>0)
      {
        if(vc[begin1] <= vc[begin2])
        {
          tmp[k++] = vc[begin1++];
        }
        else
        {
          tmp[k++] = vc[begin2++];
        }
      }

      while(end1-begin1 > 0)
      {
        tmp[k++] = vc[begin1++];
      }
      while(end2-begin2 > 0)
      {
        tmp[k++] = vc[begin2++];
      }
    }

    for(size_t i = 0; i<vc.size(); ++i)
    {
      vc[i] = tmp[i];
    }
    gap*=2;
  }
}

//void MergeSort(vector<int>& vc){
//  vector<int> tmp;
//  tmp.resize(vc.size());
//  _MergeSort(vc, tmp, 0, vc.size());
//}

void _MergeSort(vector<int>& vc, vector<int>& tmp, int begin, int end){
  int midi = begin+(end-begin)/2;
  int begin1 = begin;
  int end1 = midi;
  int begin2 = midi;
  int end2 = end;

  if(end1 - begin1 > 1)
  {
    _MergeSort(vc, tmp, begin1, end1);
  }
  if(end2 - begin2 > 1)
  {
    _MergeSort(vc, tmp, begin2, end2);
  }

  int k = begin;
  while(end1-begin1>0 && end2-begin2>0)
  {
    if(vc[begin1] <= vc[begin2])
    {
      tmp[k++] = vc[begin1++];
    }
    else
    {
      tmp[k++] = vc[begin2++];
    }
  }

  while(end1-begin1 > 0)
  {
    tmp[k++] = vc[begin1++];
  }
  while(end2-begin2 > 0)
  {
    tmp[k++] = vc[begin2++];
  }

  for(int i = begin; i<end; ++i)
  {
    vc[i] = tmp[i];
  }
}

void InsertSort(vector<int>& vc, int left, int right){
  for(int i = left; i<right-1; ++i){
    int end = i;
    int x = vc[end+1];
    while(end >= left)
    {
      if(x < vc[end])
      {
        vc[end+1] = vc[end];
        --end; //1.
      }
      else{
        break;
      }
    }
    vc[end+1] = x; //2.
  }
}

void ShellSort(vector<int>& vc){
  int gap = vc.size();
  while(gap > 1)
  {
    gap = gap/3+1;

    for(size_t i = 0; i<vc.size()-gap; ++i){
      int end = i;
      int x = vc[end+gap];
      while(end >= 0)
      {
        if(x < vc[end])
        {
          vc[end+gap] = vc[end];
          end-=gap; //1.
        }
        else{
          break;
        }
      }
      vc[end+gap] = x; //2.
    }
  }
}

void AdjustDown(vector<int>& vc, int sz, int parent){
  int child = parent*2+1;
  while(child < sz)
  {
    if(child+1 < sz && vc[child+1] > vc[child])
    {
      ++child;
    }
    if(vc[child] > vc[parent])
    {
      swap(vc[child], vc[parent]);
      parent = child;
      child = parent*2+1;
    }
    else{
      break;
    }
  }
}

void HeapSort(vector<int>& vc){
  for(int i = (vc.size()-2)/2; i>=0; --i)
  {
    AdjustDown(vc, vc.size(), i);
  }

  for(int end = vc.size()-1; end>0; --end)
  {
    swap(vc[0], vc[end]);
    AdjustDown(vc,end,0);
  }
}

void _QuickSort(vector<int>& vc, int begin, int end);
int SegMent(vector<int>& vc, int begin, int end);

void QuickSort(vector<int>& vc){
  _QuickSort(vc, 0, vc.size());
}

//void QuickSort(vector<int>& vc){
//  stack<int> st;
//  st.push(0);
//  st.push(vc.size());
//
//  while(!st.empty())
//  {
//    int end = st.top(); st.pop();
//    int begin = st.top(); st.pop();
//    
//    if(end - begin < 15)
//    {
//      InsertSort(vc, begin, end);        
//      continue;
//    }
//    int div = SegMent(vc, begin, end);
//    if(div-begin > 1)
//    {
//      st.push(begin);
//      st.push(div);
//    }
//    if(end-(div+1) > 1)
//    {
//      st.push(div+1);
//      st.push(end);
//    }
//
//  }
//}

void _QuickSort(vector<int>& vc, int begin, int end){
  if(end - begin < 15)
  {
    InsertSort(vc, begin, end);        
    return;
  }
  int div = SegMent(vc, begin, end);
  if(div-begin > 1)
  {
    _QuickSort(vc, begin, div);
  }
  if(end-(div+1) > 1)
  {
    _QuickSort(vc, div+1, end);
  }
}

int GetMidIndex(vector<int>& vc, int left, int right){
  int midi = left+(right-left)/2;
  int tmp1 = vc[left] > vc[midi]?left:midi;
  int tmp2 = vc[right] > vc[midi]?right:midi;
  return vc[tmp1] > vc[tmp2]? tmp2 : tmp1;
}

int SegMent(vector<int>& vc, int begin, int end){
  int midi = GetMidIndex(vc, begin, end-1); 
  if(midi != begin)
  {
    swap(vc[begin], vc[midi]);
  }

  int keyi = begin;
  int prev= begin;
  int cur = begin+1;
  while(cur < end)
  {
    if(vc[cur] < vc[keyi] && cur != ++prev)
    {
      swap(vc[cur], vc[prev]);
    }
    ++cur;
  }
  swap(vc[keyi], vc[prev]);
  return prev;
}
